package com.my.algorithmlearning.leetcode;

import org.apache.commons.collections4.ComparatorUtils;
import org.apache.commons.lang3.StringUtils;
import org.springframework.util.Assert;

import java.util.*;

/**
 * @ClassName Medium_15_ThreeSum
 * @Description Medium_15_ThreeSum
 * @Author wanghaiwei
 * @Date 2023/2/3 10:29
 */
public class Medium_15_ThreeSum {
    public List<List<Integer>> threeSumSlow(int[] nums) {
        if (nums == null) {
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        Map<Integer, Map<Integer, Integer>> triplets = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                break;
            }
            this.twoSum(nums, i + 1, nums[i], triplets);
        }
        List<List<Integer>> result = new ArrayList<>();
        for (Map.Entry<Integer, Map<Integer, Integer>> e : triplets.entrySet()) {
            Map<Integer, Integer> pairValue = e.getValue();
            for (Map.Entry<Integer, Integer> tmp : pairValue.entrySet()) {
                List<Integer> oneTriplet = new ArrayList<>();
                oneTriplet.add(e.getKey());
                oneTriplet.add(tmp.getKey());
                oneTriplet.add(tmp.getValue());
                result.add(oneTriplet);
            }
        }
        return result;
    }

    private void twoSum(int[] nums, int beginIdx, int currNum, Map<Integer, Map<Integer, Integer>> triplets) {
        Integer targetSum = currNum * -1;
        Map<Integer, Integer> numIdx = new HashMap<>();
        for (int i = beginIdx; i < nums.length; i++) {
            Integer targetForI = targetSum - nums[i];
            if (numIdx.containsKey(targetForI)) {
                int[] sortTriplet = sortTriplet(currNum, nums[i], nums[numIdx.get(targetForI)]);
                Map<Integer, Integer> value = triplets.getOrDefault(sortTriplet[0], new HashMap<>());
                value.put(sortTriplet[1], sortTriplet[2]);
                triplets.put(sortTriplet[0], value);
            } else {
                numIdx.put(nums[i], i);
            }
        }
    }

    private int[] sortTriplet(int fst, int secd, int third) {
        int[] result = new int[]{fst, secd, third};
        Arrays.sort(result);
        return result;
    }

    public List<List<Integer>> threeSumFast(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int idx = 0; idx < nums.length - 2; idx++) {
            if (nums[idx] > 0) {
                break;
            }
            if (idx > 0 && nums[idx] == nums[idx - 1]) {
                continue;
            }
            int i = idx + 1;
            int j = nums.length - 1;
            while (i < j) {
                int sum = nums[idx] + nums[i] + nums[j];
                if (sum < 0) {
                    while (i < j && nums[i] == nums[++i]) ;
                } else if (sum > 0) {
                    while (i < j && nums[j] == nums[--j]) ;
                } else {
                    result.add(Arrays.asList(nums[idx], nums[i], nums[j]));
                    while (i < j && nums[i] == nums[++i]) ;
                    while (i < j && nums[j] == nums[--j]) ;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Medium_15_ThreeSum solution = new Medium_15_ThreeSum();
        List<List<Integer>> result = solution.threeSumSlow(new int[]{-1, 0, 1, 2, -1, -4});
        Assert.isTrue(2 == result.size(), "threeSumSlow[-1,0,1,2,-1,-4]，计算错误，结果集长度应该是2，现在是：" + result.size());
        result.get(0).sort(Comparator.naturalOrder());
        String triplet1 = StringUtils.join(result.get(0), ",");
        Assert.isTrue("-1,-1,2".equals(triplet1) || "-1,0,1".equals(triplet1)
                , "threeSumSlow[-1,0,1,2,-1,-4]，计算错误，预期是[[-1,-1,2],[-1,0,1]]，现在出现了结果集以外的结果：" + triplet1);
        String triplet2 = StringUtils.join(result.get(1), ",");
        Assert.isTrue("-1,-1,2".equals(triplet2) || "-1,0,1".equals(triplet2)
                , "threeSumSlow[-1,0,1,2,-1,-4]，计算错误，预期是[[-1,-1,2],[-1,0,1]]，现在出现了结果集以外的结果：" + triplet2);

        result = solution.threeSumFast(new int[]{-1, 0, 1, 2, -1, -4});
        Assert.isTrue(2 == result.size(), "threeSumFast[-1,0,1,2,-1,-4]，计算错误，结果集长度应该是2，现在是：" + result.size());
        result.get(0).sort(Comparator.naturalOrder());
        triplet1 = StringUtils.join(result.get(0), ",");
        Assert.isTrue("-1,-1,2".equals(triplet1) || "-1,0,1".equals(triplet1)
                , "threeSumFast[-1,0,1,2,-1,-4]，计算错误，预期是[[-1,-1,2],[-1,0,1]]，现在出现了结果集以外的结果：" + triplet1);
        triplet2 = StringUtils.join(result.get(1), ",");
        Assert.isTrue("-1,-1,2".equals(triplet2) || "-1,0,1".equals(triplet2)
                , "threeSumFast[-1,0,1,2,-1,-4]，计算错误，预期是[[-1,-1,2],[-1,0,1]]，现在出现了结果集以外的结果：" + triplet2);
    }
}
